package com.lovely602.algorithm.leetcode.basicprogramming50;


/**
 * 459. 重复的子字符串
 * <p>
 * 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
 * <p>
 * 示例 1:
 * <p>
 * 输入: s = "abab"
 * 输出: true
 * 解释: 可由子串 "ab" 重复两次构成。
 * 示例 2:
 * <p>
 * 输入: s = "aba"
 * 输出: false
 * 示例 3:
 * <p>
 * 输入: s = "abcabcabcabc"
 * 输出: true
 * 解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 104
 * <p>
 * s 由小写英文字母组成
 *
 * @author lizhixing
 */
public class Question05 {

    public static void main(String[] args) {
        String s = "abcabc";
        Question05 question05 = new Question05();
        boolean substringPattern = question05.repeatedSubstringPattern(s);
        System.out.println("substringPattern：" + substringPattern);
        boolean repeatedSubstringPatternEnum = question05.repeatedSubstringPatternEnum(s);
        System.out.println("repeatedSubstringPatternEnum：" + repeatedSubstringPatternEnum);
    }

    public boolean repeatedSubstringPattern(String s) {

        return (s + s).indexOf(s, 1) != s.length();
    }

    /**
     * 如果一个长度为 n 的字符串 s 可以由它的一个长度为 n
     * ′
     * 的子串 s
     * ′
     * 重复多次构成，那么：
     * <p>
     * n 一定是 n
     * ′
     * 的倍数；
     * <p>
     * s
     * ′
     * 一定是 s 的前缀；
     * <p>
     * 对于任意的 i∈[n
     * ′
     * ,n)，有 s[i]=s[i−n
     * ′
     * ]。
     * <p>
     * 也就是说，s 中长度为 n
     * ′
     * 的前缀就是 s
     * ′
     * ，并且在这之后的每一个位置上的字符 s[i]，都需要与它之前的第 n
     * ′
     * 个字符 s[i−n
     * ′
     * ] 相同。
     */
    public boolean repeatedSubstringPatternEnum(String s) {

        int n = s.length();
        for (int i = 1; i * 2 <= n; ++i) {
            if (n % i == 0) {
                boolean match = true;
                for (int j = i; j < n; ++j) {
                    if (s.charAt(j) != s.charAt(j - i)) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    return true;
                }
            }
        }
        return false;

    }

}
